import javax.xml.crypto.Data;

/**
 * 归并排序
 * 思想：先将数组无限均分到不能再分，然后再将均分的两个数组进行合并
 * @author HuRui
 * create on 2018/12/27 9:03 PM
 */
public class MergeSort {
    public void sort(Integer[] array) {
        if (array == null) {
            return;
        }
        int len = array.length;
        merge(array,0,len-1);
    }

    private void merge(Integer[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid =(l+r)/2;
        merge(array, l, mid);
        merge(array, mid + 1, r);
        move(array,l,mid,r);
    }

    private void move(Integer[] array, int l, int mid, int r) {
        Integer[] aux = new Integer[r - l + 1];
        for (int i = l; i <= r ; i++) {
            aux[i - l] = array[i];
        }
//        System.out.println("aux:");
//        DataUtil.printArray(aux);
        int i = l,j=mid+1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                array[k] = aux[j-l];
                j++;
            } else if (j > r) {
                array[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                array[k] = aux[i - l];
                i++;
            } else {
                array[k] = aux[j - l];
                j++;
            }
        }
//        System.out.println("array:");
//        DataUtil.printArray(array);
    }

    public static void main(String[] args){
        Integer[] array = DataUtil.randomArray(1000, 1, 50);
        Integer[] arrayCopy = new Integer[1000];
        DataUtil.copyArray(array,arrayCopy);
        MergeSort mergeSort = new MergeSort();
        long l = System.currentTimeMillis();
        mergeSort.sort(array);
        long l1 = System.currentTimeMillis();
        System.out.println("mergeSort:" + (l1 - l));
        BubbleSort.sort(arrayCopy);
        long l2 = System.currentTimeMillis();
        System.out.println("dubbleSort:"+(l2-l1));
        System.out.println("倍数:" + (l2 - l1) / (l1 - l));
    }
}
